{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Unique Categories"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfCategories"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #唯一类别的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现给定一个整数 <code>n</code> 和一个 <code>CategoryHandler</code> 类的对象 <code>categoryHandler</code> 。</p>\n",
    "\n",
    "<p>有 <code>n&nbsp;</code> 个元素，编号从 <code>0</code> 到 <code>n - 1</code>。每个元素都有一个类别，你的任务是找出唯一类别的数量。</p>\n",
    "\n",
    "<p><code>CategoryHandler</code> 类包含以下方法，可能对你有帮助：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>boolean haveSameCategory(integer a, integer b)</code>：如果 <code>a</code> 和 <code>b</code> 属于相同的类别，则返回 <code>true</code>，否则返回 <code>false</code>。同时，如果 <code>a</code> 或 <code>b</code> 不是有效的数字（即大于等于 <code>n</code> 或小于 <code>0</code>），它也会返回 <code>false</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回&nbsp;<em>唯一类别的数量</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 6, categoryHandler = [1,1,2,2,3,3]\n",
    "<strong>输出：</strong>3\n",
    "<b>解释：</b>这个示例中有 6 个元素。前两个元素属于类别 1，接下来两个属于类别 2，最后两个元素属于类别 3。所以有 3 个唯一类别。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, categoryHandler = [1,2,3,4,5]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>这个示例中有 5 个元素。每个元素属于一个唯一的类别。所以有 5 个唯一类别。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, categoryHandler = [1,1,1]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>这个示例中有 3 个元素。它们全部属于同一个类别。所以只有 1 个唯一类别。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-unique-categories](https://leetcode.cn/problems/number-of-unique-categories/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-unique-categories](https://leetcode.cn/problems/number-of-unique-categories/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[1,1,2,2,3,3]', '5\\n[1,2,3,4,5]', '3\\n[1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        # cat_hash_set = {0}\n",
    "        # for i in range(1, n):\n",
    "        #     for idx, key in enumerate(cat_hash_set.copy()):\n",
    "        #         if categoryHandler.haveSameCategory(i, key):\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             if idx == len(cat_hash_set) - 1:\n",
    "        #                 cat_hash_set.add(i)\n",
    "        # return len(cat_hash_set)\n",
    "\n",
    "\n",
    "        # cat_hash_set = set()\n",
    "        # def is_in_hash_set(ele: int):\n",
    "        #     for i in cat_hash_set:\n",
    "        #         if categoryHandler.haveSameCategory(i,ele): \n",
    "        #             return False\n",
    "        #     return True\n",
    "        # for i in range(n):\n",
    "        #     if is_in_hash_set(i): \n",
    "        #         cat_hash_set.add(i)\n",
    "        # return len(cat_hash_set)\n",
    "\n",
    "        dc = set()\n",
    "        for i in range(n):\n",
    "            for j in dc:\n",
    "                if categoryHandler.haveSameCategory(i,j): \n",
    "                    break\n",
    "            # 注意else在if前\n",
    "            else: \n",
    "                dc.add(i)\n",
    "        return len(dc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        r = 0\n",
    "        for i in range(n):\n",
    "            t = 0\n",
    "            for j in range(i+1, n):\n",
    "                if categoryHandler.haveSameCategory(i, j):\n",
    "                    t += 1\n",
    "            if t == 0:\n",
    "                r += 1\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        # cat_hash_set = {0}\n",
    "        # for i in range(1, n):\n",
    "        #     for idx, key in enumerate(cat_hash_set.copy()):\n",
    "        #         if categoryHandler.haveSameCategory(i, key):\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             if idx == len(cat_hash_set) - 1:\n",
    "        #                 cat_hash_set.add(i)\n",
    "        # return len(cat_hash_set)\n",
    "\n",
    "\n",
    "        cat_hash_set = set()\n",
    "        def is_in_hash_set(ele: int):\n",
    "            for i in cat_hash_set:\n",
    "                if categoryHandler.haveSameCategory(i,ele): \n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            if is_in_hash_set(i): \n",
    "                cat_hash_set.add(i)\n",
    "        return len(cat_hash_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, cat: Optional['CategoryHandler']) -> int:\n",
    "\n",
    "        nums = [0 for i in range(n)]\n",
    "        id = 1\n",
    "        for i in range(n-1):\n",
    "            if nums[i]:\n",
    "                continue\n",
    "            nums[i] = id\n",
    "            for j in range(i+1, n):\n",
    "                if cat.haveSameCategory(i, j):\n",
    "                    nums[j] = id\n",
    "            id += 1\n",
    "        return len(set(nums))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        dc = set()\n",
    "        def g(a):\n",
    "            for i in dc:\n",
    "                if categoryHandler.haveSameCategory(i,a): return False\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            if g(i): dc.add(i)\n",
    "        return len(dc)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "\n",
    "class IdentityDefaultDict(defaultdict):\n",
    "    '''\n",
    "    该类用于处理并查集初始化的恒等映射\n",
    "    '''\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n=None):\n",
    "        self.parent = IdentityDefaultDict()\n",
    "        if n: self.parent = list(range(n))\n",
    "            \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y: self.parent[x] = y\n",
    "    def count_groups(self):\n",
    "        return len(set(self.find(x) for x in self.parent))\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, c: Optional['CategoryHandler']) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if c.haveSameCategory(i, j):\n",
    "                    uf.merge(i, j)\n",
    "        return uf.count_groups()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        #一眼并查集,只是题目表述有点抽象,给你一个接口用来判断是否连通,有点新奇。\n",
    "        kkk=setUnion(n)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if categoryHandler.haveSameCategory(i,j):\n",
    "                    kkk.union(i,j)\n",
    "        return kkk.setCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        result, s = 0, {*range(n)}\n",
    "        while s:\n",
    "            i = s.pop()\n",
    "            tmp = {j for j in s if categoryHandler.haveSameCategory(i, j)}\n",
    "            s -= tmp\n",
    "            result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        res=n\n",
    "        pa=list(range(n))\n",
    "        def find(k):\n",
    "          if pa[k]!=k:pa[k]=find(pa[k])\n",
    "          return pa[k]\n",
    "        def union(x,y):\n",
    "          px,py=find(x),find(y)\n",
    "          if px==py:return \n",
    "          pa[py]=pa[px]\n",
    "          nonlocal res\n",
    "          res-=1\n",
    "        for i in range(n):\n",
    "          for j in range(i+1,n):\n",
    "            if categoryHandler.haveSameCategory(i,j):\n",
    "              union(i,j)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        dc = set()\n",
    "        for i in range(n):\n",
    "            for j in dc:\n",
    "                if categoryHandler.haveSameCategory(i,j): break\n",
    "            else: dc.add(i)\n",
    "        return len(dc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        fa=[i for i in range(n)]\n",
    "        def find(x):\n",
    "            if x!=fa[x]:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(a,b):\n",
    "            if find(a)!=find(b):\n",
    "                fa[find(a)]=find(b)\n",
    "        c=collections.Counter()\n",
    "        for a in range(n):\n",
    "            for b in range(a+1,n):\n",
    "                if categoryHandler.haveSameCategory(a,b):\n",
    "                    union(a,b)\n",
    "        for i in range(n):\n",
    "            c[find(i)]+=1\n",
    "        return len(list(c.keys()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        cat_hash_set = {0}\n",
    "        for i in range(1, n):\n",
    "            for idx, key in enumerate(cat_hash_set.copy()):\n",
    "                if categoryHandler.haveSameCategory(i, key):\n",
    "                    break\n",
    "                else:\n",
    "                    if idx == len(cat_hash_set) - 1:\n",
    "                        cat_hash_set.add(i)\n",
    "        return len(cat_hash_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        unique = set()\n",
    "        for x in range(n):\n",
    "            if any(categoryHandler.haveSameCategory(x, y) for y in unique): continue\n",
    "            unique.add(x)\n",
    "        return len(unique)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        result, s = 0, {*range(n)}\n",
    "        while s:\n",
    "            i = s.pop()\n",
    "            s -= {j for j in s if categoryHandler.haveSameCategory(i, j)}\n",
    "            result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class IdentityDefaultDict(defaultdict):\n",
    "    '''\n",
    "    该类用于处理并查集初始化的恒等映射\n",
    "    '''\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = IdentityDefaultDict()\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y: self.parent[x] = y\n",
    "    def count_groups(self):\n",
    "        return len(set(self.find(x) for x in self.parent))\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, c: Optional['CategoryHandler']) -> int:\n",
    "        uf = UnionFind()\n",
    "        for i in range(n):\n",
    "            uf.merge(i, -i-1)\n",
    "            for j in range(n):\n",
    "                if c.haveSameCategory(i, j):\n",
    "                    uf.merge(i, j)\n",
    "        return uf.count_groups()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def union(i, j):\n",
    "            if fa[i] != fa[j]:\n",
    "                fa[j] = i\n",
    "\n",
    "        fa = {}\n",
    "        for i in range(n):\n",
    "            fa[i] = i\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if i != j and categoryHandler.haveSameCategory(i, j):\n",
    "                    union(i, j)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if fa[i] == i:\n",
    "                res +=  1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a category handler.\n",
    "# class CategoryHandler:\n",
    "#     def haveSameCategory(self, a: int, b: int) -> bool:\n",
    "#         pass\n",
    "class Solution:\n",
    "    def numberOfCategories(self, n: int, categoryHandler: Optional['CategoryHandler']) -> int:\n",
    "        store = set()\n",
    "        for i in range(n):\n",
    "            for j in store:\n",
    "                if categoryHandler.haveSameCategory(i, j):\n",
    "                    break\n",
    "            else:\n",
    "                store.add(i)\n",
    "        return len(store)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
